package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

/**
 * 求后续表达式形式的运算的值
 * @author 付大石
 */
public class Main {

    public static void main(String[] args) {
        
        String[] infixExp = {"(","(","1","+","2",")","*","(","(","3","-","4",")","*","(","5","-","6",")",")",")"};
        String[] postfixExp = infixToPostfix(infixExp).split(" ");
        Stack<Double> stack = new LinkedStack<>();
        for(String item : postfixExp) {
            if(item.equals("+")) {
                double v1 = stack.pop();
                double v2 = stack.pop();
                stack.push(v2+v1);
            } else if(item.equals("-")) {
                double v1 = stack.pop();
                double v2 = stack.pop();
                stack.push(v2-v1);
            } else if(item.equals("*")) {
                double v1 = stack.pop();
                double v2 = stack.pop();
                stack.push(v2*v1);
            } else if(item.equals("/")) {
                double v1 = stack.pop();
                double v2 = stack.pop();
                stack.push(v2/v1);
            } else {
                stack.push(Double.parseDouble(item));
            }
        }
        double result =stack.pop();
        if(!stack.isEmpty()) {
            throw new RuntimeException("后缀表达式解析错误");
        } else {
            System.out.println(result);
        }
        
    }
    
    private static String infixToPostfix(String[] infixExp) {
        
        Stack<String> operationStack = new LinkedStack<>();
        StringBuilder postfixExp = new StringBuilder();
        for(String item : infixExp) {
            if(item.equals("(")) {
                //nothing to do
            } else if(item.equals("+")) {
                operationStack.push(item);
            } else if(item.equals("-")) {
                operationStack.push(item);
            } else if(item.equals("*")) {
                operationStack.push(item);
            } else if(item.equals("/")) {
                operationStack.push(item);
            } else if(item.equals(")")) {
                postfixExp.append(operationStack.pop()).append(" ");
            } else {
                postfixExp.append(item).append(" ");
            }
        }
        return postfixExp.toString();
    }
}
